"""
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. 
"""

class Solution:
    # @param {string} s
    # @return {integer}
    def longestValidParentheses(self, s):
        l = len(s)
        st = []
        ma = {} # 
        ans = 0
        for i in range(len(s)):
            if len(st) == 0 or s[i] == '(':
                st.append(s[i])
                continue
            elif st[-1] == '(' and s[i] == ')':
                ex = 0
                key = len(st)-1
                if ma.has_key(key+1):
                    ex = ma[key+1]
                    ma[key+1] = 0
                if ma.has_key(key):
                    ma[key] += 2
                else:
                    ma[key] = 2
                ma[key] += ex
                st.pop()
            else:
                st.append(s[i])
        for k in ma:
            ans = max(ans, ma[k])
        return ans

if __name__ == '__main__':
    print Solution().longestValidParentheses(')()()))')
    print Solution().longestValidParentheses('(()')
